区块链中一种基于NP难解问题的工作量证明(PoW)算法

这篇文章描述如何基于一个NP难解问题：求解二次多元多项式方程，构造一个兼具计算困难及内存困难的区块链PoW算法。

构成区块链技术体系中最为重要的一点就是共识算法:区块链网络中，如何让不同节点达成共识。区块链目前主要的共识算法有PoW，PoS，DPoS，PBFT，基于VRF的共识等等。PoW是第一个也是区块链中目前应用最为广泛的共识算法，Bitcoin，Ethereum，Litecoin等都以此算法作为共识算法，其在大量算力的支持下，具有稳定，安全，去中心化的优良特性。

使用SHA256等构造的PoW原本设想是基于CPU挖矿的，使得每个人都有平等的权利获取记账权，从而充分达到去中心化的目的。然而，但随着 GPU，FPGA，以及 ASIC 矿机(如比特大陆的蚂蚁矿机S7，S9等)的出现，挖矿计算能力越来越集中，使得记账的权利越来越集中在少数计算能力强大的矿工手中，有违中本聪最先提出的去中心化网络的构想。

为了达到去中心化的特点，防止算力过于集中，后续提出的PoW算法所基于的哈希算法一般都具有内存困难属性，使得构造相关的ASIC芯片代价过于高昂，如莱特币中使用的Scrypt，ZCash中使用的Equihash。

另一方面，有限域上求解随机多元多次方程是一个被广泛深入研究的问题，求解这一类问题的算法有XL算法，孙子算法，以及基于求解Grobner基的算法，其中基于Grobner基求解的F4，F5算法是求解这样一组方程组中最为高效的算法，可以用于攻击多变量公钥密码学算法，AES等。

此外，使用F4，F5等算法求解限域上随机多元多次方程组是一个困难问题，既具有计算困难性也具有内存困难性，十分适合用来构造PoW的哈希算法，而在其他抗ASIC的PoW算法设计中，也都选择使用既具有计算困难性以及内存困难性的困难问题来构造哈希算法，如Zcash中的Equihash使用了生日问题作为PoW哈希函数的构造。

目前为止，已知的区块链PoW算法中，还没有使用基于求解有限域多元二次多项式方程组作为哈希函数构造的。

其中PoW是通过计算一个数学上的困难问题来达到共识的，通常用哈希函数作为基础困难问题求解如下的解

Hash(X)

PoW_Target的值地大小则决定了解这个困难问题的难度，Pow_Target的值越小，难度越大。

比如，如果用16进制表示一个256bit位的PoW_Target吗，且值为：

"0x00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"

那么求解这个困难值，平均需要穷举Nonce值的次数为：

0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff /Pow_Target=256

如果Pow_Target的值为

"0x007fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"

那么求解这个困难值，平均需要穷举Nonce值的次数为：

0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff /Pow_Target=512

需要穷举计算的次数越多，说明难度越大，所以Pow_Target的值越小，难度越大。

根据，可以定义难度值Difficulty为

Difficulty=最大目标值/Pow_Target

其中最大目标值表示求解困难问题时，Pow_Target可能地最大取值，也就相当于定义了生成区块时，求解困难问题的最小难度值。在测试网时，这个值可以设大一点(即生成区块的最低难度设小一点)。

比特币主网的最大目标值为：0x00000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffff；

从难度值与目标值的关系公式来看，这两者之间可以相互转化，且成反比关系。

PoW的难度值Diffculty一般与全网的算力HashRate有关，如果全网的算力增大的话，那么求解PoW困难问题的难度值也应该增大。

seed=SHA256(prev_block+Nonce),

其中Nonce初始值为0。

2. 随机数序列生成：在生成种子数seed之后，代入伪随机数生成随机数序列PRG(seed , i), 其中 i = 0, 1, …..

3. 有限域随机多元二次方程组生成：首先选定方程组参数, 包括有限域GF(q), 变量数n，方程数m，为确定唯一解，一般m=n，我们这里也选取m=n。那么确定这一组随机方程，需要的随机系数个数为二次项系数+一次项系数+常量系数+等式右边常量，所以所需随机数为 n^2/2\times m +n \times m + m + m = n^3 /2 + (n+2) n 。使用第2步中的随机数序列生成方程组的系数。

生成的方程组为：

4. 求解方程：使用目前最为高效的有限域随机多元二次方程组求解算法：F4和F5，求解上述方程组，输出最终解 X=(x_1,x_2, ..., x_n) 。

5.计算解的哈希值：Hash=sha256(X)。

6.计算当前PoW目标值PoW_target: 使用难度调整算法(DAA)作为核心功能程序实现，使用以往区块的难度值作为输入，假设当前区块高度为i，那么生成当前区块工作量需要达到的难度值 D_i=DAA(D_{i-1}, D_{i-2}, D_{i-3},...) 。其中DAA的算法没有限定，使用主流PoW主流区块链的DAA或者自行设计均可。那么

PoW\_target = PoWLimit/D_i

其中PoWLimit为DAA算法中设定的最小的工作量。

7. 判断5中解的Hash是否小于PoW_target，如果小于，那么PoW过程结束，否则重新选取Nonce=Nonce+1值，从1开始重新计算Hash，直到满足条件为止。

求解有限域上多元二次方程组是NP难解问题，其兼具计算困难性也具有内存困难性，使用其构造PoW算法，相比比特币的使用SHA256作为PoW，能够在一定程度上防止算力集中在少数矿工手上，更加去中心化。

此外，使用其他的困难问题，使用类似思路，也可以构造出PoW算法。

PoW由于消耗资源过大，并不环保，目前新的区块链应该很少有用PoW作为共识算法的了。

文章主体内容写于2019年初，如信息有误，麻烦指正。